/*
https://leetcode.cn/problems/longest-well-performing-interval/solution/qian-zhui-he-dan-diao-zhan-python3-by-smoon1989/
 */
import java.util.Stack;

public class Solution1124 {
    public int longestWPI(int[] hours) {
        int[] num=new int[hours.length];
        for (int i=0;i<hours.length;i++){
            if (hours[i]>8){
                num[i]=1;
            }else {
                num[i]=-1;
            }
        }
        int[] sum=new int[num.length+1];
        for (int i=0;i<num.length;i++){
            sum[i+1]=sum[i]+num[i];
        }
        Stack<Integer> stack=new Stack<>();
        for (int i=0;i<=num.length;i++){
            if (stack.isEmpty()||sum[stack.peek()]>sum[i]){
                stack.push(i);
            }
        }
        int ans=0;
        for (int i=num.length;i>=0;i--){
            while (!stack.isEmpty() && sum[i]-sum[stack.peek()]>0){
                ans=Math.max(ans,i-stack.peek());
                stack.pop();
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1124().longestWPI(new int[]{9,9,6,0,6,6,9}));
    }
}
